package solution

import "myleecode/solution/common"

// 41. 缺失的第一个正数
//给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
//进阶：你可以实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案吗？

func Leecode41_firstMissingPositive(nums []int) int {
	// 方法一： 类似哈希
	m := make(map[int]struct{})
	for _, n := range nums {
		m[n] = struct{}{}
	}
	i := 0
	for i=1; i<=len(nums); i++ {
		if _, ok := m[i]; !ok {
			return i
		}
	}

	// 地址哈希算法
	return i
}

// 42. 接雨水
// 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水
//输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
//输出：6
//解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
func Leecode42_trap(nums []int) int {
	// 逐行扫描
	return 0
}

// 45. 跳跃游戏
//给定一个非负整数数组，你最初位于数组的第一个位置。
//
//数组中的每个元素代表你在该位置可以跳跃的最大长度。
//你的目标是使用最少的跳跃次数到达数组的最后一个位置。
//示例:
//
//输入: [2,3,1,1,4]
//输出: 2
//解释: 跳到最后一个位置的最小跳跃数是 2。
// 从下标为 0 跳到下标为 1 的位置，跳1步，然后跳3步到达数组的最后一个位置。

func Leecode45_jump(nums []int) int {
	end, maxPosition, step := 0, 0, 0
	for i:=0; i<len(nums)-1; i++ {
		maxPosition = common.Max(maxPosition, nums[i]+1)
		if i == end {
			end = maxPosition
			step++
		}
	}
	return step
}

// 46. 全排列
// 给定的数字没有重复
// 回溯算法
func Leecode46_permute(nums []int) [][]int {
	var result [][]int
	var ans []int
	check := make([]bool, len(nums))
	var backtrack func()
	backtrack = func() {
		if len(ans) == len(nums) {
			tmp := make([]int, len(ans))
			copy(tmp, ans[:])
			result = append(result, tmp)
		}
		for i:=0; i<len(nums); i++ {
			if !check[i] {
				check[i] = true
				ans = append(ans, nums[i])
				backtrack()
				check[i] = false
				ans = ans[:len(ans)-1]
			}
		}
	}
	backtrack()
	return result
}
